#!/usr/bin/python
# -*- coding:utf-8 -*-
#桶排序
#@author: wklken@yeah.net


def bucket_sort(l):
    #寻找最大
    max = l[0]
    for i in l:
        if i > max:
            max = i
    
    #决定桶数  50 为1个桶
    result = [ [] for i in range((max+49)/50)]
    print result
    for value in l:
        index = value/50
        if len(result[index]) == 0:
            result[index].append(value)
            continue
        i = len(result[index])
        while result[index][i-1] > value and i > 0:
            i -= 1
        print "old",result[index],"insert into ",i," value",value
        result[index].insert(i,value)
    return reduce(lambda x,y: x + y, result)

l = [18, 20, 3, 7, 99, 87, 120, 33, 19, 31]

print bucket_sort(l)
    